package listnode;

public class _86_分隔链表 {


    /**
     * 给定一个链表和一个特定值 x，对链表进行分隔，使得所有小于 x 的节点都在大于或等于 x 的节点之前。
     * <p>
     * 你应当保留两个分区中每个节点的初始相对位置。
     * <p>
     *  
     * <p>
     * 示例:
     * <p>
     * 输入: head = 1->4->3->2->5->2, x = 3
     * 输出: 1->2->2->4->3->5
     * <p>
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/partition-list
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     *
     * @param head
     * @param x
     * @return
     */
    public static ListNode partition(ListNode head, int x) {
        ListNode big = new ListNode();
        ListNode small = new ListNode();
        ListNode presmall = small;
        ListNode prebig = big;
        while (head!=null){
            if (head.val >= x) {
                big.next = new ListNode(head.val);
                big = big.next;
            }else {
                small.next = new ListNode(head.val);
                small = small.next;
            }
            head = head.next;
        }
        small.next = prebig.next;
        return presmall.next;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(4);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(2);
        ListNode n5 = new ListNode(5);
        ListNode n6 = new ListNode(2);
        n1.next = n2;
        n2.next = n3;
        n3.next=n4;
        n4.next=n5;
        n5.next=n6;
        ListNode partition = partition(n1, 3);
    }
}
